/**
 * 堆数据结构使用示例 (zh-heap.js)
 * 演示堆、最小堆、最大堆、优先队列的各种操作
 */

// 支持 CommonJS 和 ES 模块导入
const heapModule = require('../../zh/公共函数/zh-heap.js');
const {
  堆
} = heapModule || {
  堆: heapModule.堆 || heapModule.default
};

console.log('=== 堆数据结构 (zh-heap.js) 使用示例 ===\n');

// ===== 1. 基本堆操作 =====
console.log('1. 基本堆操作:');

// 1.1 创建空堆并插入元素
console.log('创建空堆并插入元素:');
const 基本堆 = new 堆();
基本堆.插入(5).插入(3).插入(8).插入(1).插入(10);
console.log('  堆元素:', 基本堆.取值());
console.log('  堆大小:', 基本堆.大小());
console.log('  堆顶元素:', 基本堆.查看堆顶());

// 1.2 弹出堆顶元素
const 弹出元素 = 基本堆.弹出堆顶();
console.log('  弹出堆顶元素:', 弹出元素);
console.log('  弹出后堆元素:', 基本堆.取值());

// 1.3 批量插入元素
console.log('批量插入元素 [2, 7, 4]:');
基本堆.批量插入([2, 7, 4]);
console.log('  批量插入后堆元素:', 基本堆.取值());

// 1.4 清空堆
基本堆.清空();
console.log('  清空后堆是否为空:', 基本堆.是否为空());

// ===== 2. 最小堆 =====
console.log('\n2. 最小堆:');

// 2.1 使用静态方法创建最小堆
const 最小堆 = 堆.创建最小堆([4, 1, 3, 2, 16, 9, 10, 14, 8, 7]);
console.log('  初始最小堆:', 最小堆.取值());
console.log('  堆顶元素(最小值):', 最小堆.查看堆顶());

// 2.2 最小堆排序
const 排序结果 = 最小堆.排序();
console.log('  最小堆排序结果:', 排序结果);

// ===== 3. 最大堆 =====
console.log('\n3. 最大堆:');

// 3.1 创建最大堆
const 最大堆 = 堆.创建最大堆([4, 1, 3, 2, 16, 9, 10, 14, 8, 7]);
console.log('  初始最大堆:', 最大堆.取值());
console.log('  堆顶元素(最大值):', 最大堆.查看堆顶());

// 3.2 替换堆顶元素
const 旧堆顶 = 最大堆.替换堆顶(0);
console.log('  替换堆顶旧值:', 旧堆顶);
console.log('  替换后最大堆:', 最大堆.取值());

// ===== 4. 自定义比较函数堆 =====
console.log('\n4. 自定义比较函数堆:');

// 4.1 根据对象的某个属性创建堆
const 人员数据 = [
  { 姓名: '张三', 年龄: 25 },
  { 姓名: '李四', 年龄: 30 },
  { 姓名: '王五', 年龄: 22 },
  { 姓名: '赵六', 年龄: 35 },
  { 姓名: '钱七', 年龄: 28 }
];

// 按年龄大小排序的堆
const 年龄堆 = new 堆(人员数据, (a, b) => a.年龄 - b.年龄);
console.log('  按年龄排序的堆:');
年龄堆.遍历(人员 => console.log(`    ${人员.姓名} - ${人员.年龄}岁`));

// 弹出按年龄排序的人员
console.log('  按年龄从小到大弹出人员:');
while (!年龄堆.是否为空()) {
  const 人员 = 年龄堆.弹出堆顶();
  console.log(`    ${人员.姓名} - ${人员.年龄}岁`);
}

// ===== 5. 优先队列实现 =====
console.log('\n5. 优先队列实现:');

// 5.1 创建任务优先队列
const 任务数据 = [
  { id: 1, 描述: '普通任务', 优先级: 3 },
  { id: 2, 描述: '紧急任务', 优先级: 1 },
  { id: 3, 描述: '重要任务', 优先级: 2 },
  { id: 4, 描述: '次要任务', 优先级: 4 }
];

// 优先级数字越小，优先级越高
const 任务队列 = 堆.创建优先队列((a, b) => a.优先级 - b.优先级, 任务数据);

console.log('  处理任务队列:');
while (!任务队列.是否为空()) {
  const 任务 = 任务队列.弹出堆顶();
  console.log(`    任务${任务.id}: ${任务.描述} (优先级: ${任务.优先级})`);
}

// ===== 6. 堆元素更新操作 =====
console.log('\n6. 堆元素更新操作:');

// 6.1 更新堆中指定索引的元素
const 更新堆 = new 堆([10, 20, 30, 40, 50]);
console.log('  更新前堆:', 更新堆.取值());

// 将索引2的元素(30)更新为5
更新堆.更新元素(2, 5);
console.log('  更新后堆:', 更新堆.取值());

// 6.2 查找并移除元素
const 查找堆 = new 堆([1, 3, 5, 7, 9]);
const 目标元素 = 5;
const 元素索引 = 查找堆.查找元素(目标元素);

if (元素索引 !== -1) {
  const 移除的元素 = 查找堆.移除元素(元素索引);
  console.log(`  查找并移除元素 ${目标元素}，索引: ${元素索引}`);
  console.log('  移除后堆:', 查找堆.取值());
}

// ===== 7. 堆的验证和高度 =====
console.log('\n7. 堆的验证和高度:');

// 7.1 验证堆的有效性
const 验证堆 = 堆.创建最小堆([3, 1, 2, 4, 5]);
console.log('  堆是否有效:', 验证堆.验证堆());
console.log('  堆的高度:', 验证堆.获取高度());

// 7.2 获取指定层级的元素
console.log('  层级0元素:', 验证堆.获取层级(0));
console.log('  层级1元素:', 验证堆.获取层级(1));
console.log('  层级2元素:', 验证堆.获取层级(2));

// ===== 8. 堆的遍历和迭代 =====
console.log('\n8. 堆的遍历和迭代:');

// 8.1 使用遍历方法
const 遍历堆 = 堆.创建最小堆([5, 3, 8, 1, 2]);
console.log('  堆存储顺序遍历:');
遍历堆.遍历((元素, 索引) => {
  console.log(`    索引${索引}: ${元素}`);
});

// 8.2 使用迭代器（按堆顶弹出顺序）
console.log('  迭代器遍历(堆顶弹出顺序):');
for (const 元素 of 遍历堆) {
  console.log(`    ${元素}`);
}

// 8.3 使用层级迭代（按存储顺序）
console.log('  层级迭代(存储顺序):');
for (const 元素 of 遍历堆.层级迭代()) {
  console.log(`    ${元素}`);
}

// ===== 9. 堆的高级操作 =====
console.log('\n9. 堆的高级操作:');

// 9.1 克隆堆
const 原堆 = 堆.创建最大堆([10, 20, 30]);
const 克隆堆 = 原堆.克隆();
console.log('  原堆:', 原堆.取值());
console.log('  克隆堆:', 克隆堆.取值());

// 修改原堆不影响克隆堆
原堆.弹出堆顶();
console.log('  修改后原堆:', 原堆.取值());
console.log('  克隆堆(不变):', 克隆堆.取值());

// 9.2 执行自定义操作
const 自定义堆 = 堆.创建最小堆([1, 2, 3, 4, 5]);
const 新堆 = 自定义堆.执行(数据 => 数据.filter(item => item % 2 === 0));
console.log('  原堆:', 自定义堆.取值());
console.log('  过滤偶数后的新堆:', 新堆.取值());

// ===== 10. 堆排序算法 =====
console.log('\n10. 堆排序算法:');

// 10.1 使用静态方法进行堆排序
const 待排序数组 = [4, 10, 3, 5, 1];
const 升序结果 = 堆.堆排序(待排序数组, (a, b) => a - b);
console.log('  原始数组:', 待排序数组);
console.log('  升序结果:', 升序结果);

// 降序排序
const 降序结果 = 堆.堆排序([...待排序数组], (a, b) => b - a);
console.log('  降序结果:', 降序结果);

// ===== 11. 实际应用场景 =====
console.log('\n11. 实际应用场景:');

// 11.1 实时数据流的最大/最小值
console.log('\n11.1 实时数据流的最大/最小值:');
const 数据流最大值 = 堆.创建最大堆();
const 数据流最小值 = 堆.创建最小堆();

// 模拟数据流
const 数据流 = [23, 15, 42, 8, 31, 19, 45, 2, 11];

console.log('  数据流:', 数据流);
console.log('  实时处理:');
for (const 数据 of 数据流) {
  数据流最大值.插入(数据);
  数据流最小值.插入(数据);
  console.log(`    插入 ${数据} - 当前最大值: ${数据流最大值.查看堆顶()}, 当前最小值: ${数据流最小值.查看堆顶()}`);
}

// 11.2 任务调度系统
console.log('\n11.2 任务调度系统:');
const 调度系统 = 堆.创建优先队列((a, b) => {
  // 优先级高的先执行，相同优先级按创建时间
  if (a.优先级 !== b.优先级) return a.优先级 - b.优先级;
  return a.创建时间 - b.创建时间;
});

const 创建任务 = (描述, 优先级) => {
  return {
    描述,
    优先级,
    创建时间: Date.now(),
    执行时间: null
  };
};

// 添加任务
调度系统
  .插入(创建任务('系统维护', 3))
  .插入(创建任务('错误修复', 1))
  .插入(创建任务('数据备份', 2))
  .插入(创建任务('更新缓存', 3))
  .插入(创建任务('紧急修复', 1));

console.log('  任务执行顺序:');
while (!调度系统.是否为空()) {
  const 任务 = 调度系统.弹出堆顶();
  任务.执行时间 = new Date().toLocaleTimeString();
  console.log(`    [优先级${任务.优先级}] ${任务.描述} - 执行时间: ${任务.执行时间}`);
}

// 11.3 堆实现的Top K问题
console.log('\n11.3 Top K问题:');
const topK = (数组, k) => {
  // 使用最小堆保留最大的k个元素
  const 小顶堆 = 堆.创建最小堆();
  
  for (const 元素 of 数组) {
    if (小顶堆.大小() < k) {
      小顶堆.插入(元素);
    } else if (元素 > 小顶堆.查看堆顶()) {
      小顶堆.替换堆顶(元素);
    }
  }
  
  return 小顶堆.排序().reverse(); // 从大到小返回
};

const 测试数组 = [3, 2, 1, 5, 6, 4, 8, 7, 9];
const k = 3;
const topK结果 = topK(测试数组, k);
console.log(`  数组:`, 测试数组);
console.log(`  Top ${k} 元素:`, topK结果);

// 11.4 合并K个有序数组
console.log('\n11.4 合并K个有序数组:');
const 合并K有序数组 = (数组列表) => {
  const 结果 = [];
  const 优先队列 = 堆.创建优先队列((a, b) => a.值 - b.值);
  
  // 初始化：将每个数组的第一个元素加入优先队列
  for (let i = 0; i < 数组列表.length; i++) {
    if (数组列表[i].length > 0) {
      优先队列.插入({
        值: 数组列表[i][0],
        数组索引: i,
        元素索引: 0
      });
    }
  }
  
  // 合并过程
  while (!优先队列.是否为空()) {
    const 最小元素 = 优先队列.弹出堆顶();
    结果.push(最小元素.值);
    
    // 将同一数组的下一个元素加入队列
    const 下一元素索引 = 最小元素.元素索引 + 1;
    const 当前数组 = 数组列表[最小元素.数组索引];
    
    if (下一元素索引 < 当前数组.length) {
      优先队列.插入({
        值: 当前数组[下一元素索引],
        数组索引: 最小元素.数组索引,
        元素索引: 下一元素索引
      });
    }
  }
  
  return 结果;
};

const k有序数组 = [
  [1, 4, 7],
  [2, 5, 8],
  [3, 6, 9]
];
const 合并结果 = 合并K有序数组(k有序数组);
console.log('  输入数组:', k有序数组);
console.log('  合并结果:', 合并结果);

// 11.5 堆用于计算中位数
console.log('\n11.5 动态中位数计算:');
class 中位数计算 {  
  constructor() {
    this.小顶堆 = 堆.创建最小堆(); // 存储较大的一半元素
    this.大顶堆 = 堆.创建最大堆(); // 存储较小的一半元素
  }
  
  添加(数字) {
    // 策略：大顶堆大小 >= 小顶堆大小
    if (this.大顶堆.大小() === 0 || 数字 <= this.大顶堆.查看堆顶()) {
      this.大顶堆.插入(数字);
    } else {
      this.小顶堆.插入(数字);
    }
    
    // 平衡两个堆的大小
    if (this.大顶堆.大小() > this.小顶堆.大小() + 1) {
      this.小顶堆.插入(this.大顶堆.弹出堆顶());
    } else if (this.小顶堆.大小() > this.大顶堆.大小()) {
      this.大顶堆.插入(this.小顶堆.弹出堆顶());
    }
  }
  
  获取中位数() {
    if (this.大顶堆.大小() === 0) return null;
    
    if (this.大顶堆.大小() > this.小顶堆.大小()) {
      return this.大顶堆.查看堆顶();
    } else {
      return (this.大顶堆.查看堆顶() + this.小顶堆.查看堆顶()) / 2;
    }
  }
}

const 中位数计算器 = new 中位数计算();
const 中位数测试数据 = [5, 2, 9, 1, 7, 4, 6];

console.log('  数据流:', 中位数测试数据);
console.log('  动态中位数:');
for (const 数字 of 中位数测试数据) {
  中位数计算器.添加(数字);
  console.log(`    添加 ${数字} - 当前中位数: ${中位数计算器.获取中位数()}`);
}

console.log('\n=== 所有堆数据结构示例执行完成 ===');
